#递归
class A:
    def __init__(self,value,left=None,right=None):
        self.value=value
        self.left=left
        self.right=right
g=A(7)
f=A(6)
e=A(5)
d=A(4)
c=A(3,f,g)
b=A(2,d,e)
a=A(1,b,c)

def func(a):
    if a!=None:
        print(a.value)
        func(a.left)#func(b)
        func(a.right)#func(c)
func(a)
######################################################
def funb(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    else:       #   4         3#funcb(3)+funb(2)+funcb(2)+1
        return funb(n-1)+funb(n-2)

print(funb(5))

